package main

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

func copyRandomList(head *Node) *Node {
	if head == nil {
		return head
	}
	//key前节点 value现节点
	nodeMap := make(map[*Node]*Node)
	tempPrev := head
	node := &Node{Val: head.Val}
	tempNow := node
	nodeMap[head] = node
	for tempPrev.Next != nil {
		n := &Node{Val: tempPrev.Next.Val}
		nodeMap[tempPrev.Next] = n
		tempNow.Next = n
		tempNow = tempNow.Next
		tempPrev = tempPrev.Next
	}
	tempPrev = head
	tempNow = node
	for tempPrev != nil {
		n := nodeMap[tempPrev.Random]
		tempNow.Random = n
		tempNow = tempNow.Next
		tempPrev = tempPrev.Next
	}
	return node
}

func main() {
	n5 := &Node{Val: 1}
	n4 := &Node{Val: 10, Next: n5}
	n3 := &Node{Val: 11, Next: n4}
	n2 := &Node{Val: 13, Next: n3}
	n1 := &Node{Val: 7, Next: n2}
	n2.Random = n1
	n3.Random = n5
	n4.Random = n3
	n5.Random = n1
	list := copyRandomList(n1)
	for list != nil {
		println("val:", list.Val)
		random := list.Random
		if random != nil {
			println("rand:", random.Val)
		} else {
			println("rand: nil")
		}
		list = list.Next
	}

}
